P2831 愤怒的小鸟

首先,我们得知道过原点与两点的抛物线解析式:

设该函数解析式为 y=ax2+bx+c(a<0)y=ax^2+bx+c(a < 0)且过 (0,0),(x1,y1),(x2,y2)(0,0),(x_1,y_1),(x_2,y_2) 三点。

由函数过 (0,0)(0,0)c=0c=0

函数解析式为 y=ax2+bx(a<0)y=ax^2+bx(a < 0)

{ax12+bx1=y1ax22+bx2=y2\begin{cases} {ax_1}^2+bx_1=y_1\\ {ax_2}^2+bx_2=y_2 \end{cases}

{a=y1bx1x12a=y2bx2x22\begin{cases} a=\frac{y1-bx_1}{{x_1}^2}\\ a=\frac{y2-bx_2}{{x_2}^2} \end{cases}

y1bx1x12=y2bx2x22\to \frac{y_1-bx_1}{{x_1}^2}=\frac{y_2-bx_2}{{x_2}^2}

(y1bx1)x22=(y2bx2)x12\to (y_1-bx_1)* {{x_2}^2}=(y_2-bx_2)*{{x_1}^2}

y1x22bx1x22=y2x12bx2x12\to y_1*{x_2}^2-bx_1*{x_2}^2=y_2*{x_1}^2-bx_2*{x_1}^2

bx2x12bx1x22=y2x12y1x22\to bx_2*{x_1}^2-bx_1*{x_2}^2=y_2*{x_1}^2-y_1*{x_2}^2

bx1bx2=y2x12y1x22x1x2\to bx_1-bx_2=\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2}

b=y2x12y1x22x1x2(x1x2)\to b=\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2(x_1-x_2)}

a=y1bx1x12\to a=\frac{y_1-bx_1}{{x_1}^2}

a=x2y1x1y2x1x2(x2x1)\to a=\frac{x_2*y_1-x_1*y_2}{x_1x_2(x_2-x_1)}

综上所述,函数解析式为

y=x2y1x1y2x1x2(x2x1)x2+y2x12y1x22x1x2(x1x2)xy=\frac{x_2*y_1-x_1*y_2}{x_1x_2(x_2-x_1)}x^2+\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2(x_1-x_2)}x


dfs(x,num,lon)表示处理到第x只猪,用了num只鸟,剩下lon只没有被击中\text{dfs(x,num,lon)表示处理到第$x$只猪,用了$num$只鸟,剩下$lon$只没有被击中}

剩下的就容易处理了。

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
#define eps 1e-8
#define Paird pair<double,double>

const int MAXN = 20;
int t , n , m , Ans , s;
struct node{
	double x , y;
}dex[ MAXN + 5 ] , fun[ MAXN + 5 ] , lone[ MAXN + 5 ];
Paird calc( node a , node b ) {
	double A = ( b.x * a.y - a.x * b.y ) / ( a.x * b.x * ( a.x - b.x ) ) , B = ( b.y * a.x * a.x - a.y * b.x * b.x ) / ( a.x * b.x * ( a.x - b.x ) );
	return { A , B };
}

void dfs( int x , int num , int lon ) {
	if( num + lon >= Ans ) return;
	if( x == n + 1 ) {
		Ans = num + lon;	//使用的鸟+剩下的猪各需一只鸟
		return;
	}
	
	for( int i = 1 ; i <= num ; i ++ ) //看这只猪能否被之前的一只鸟击中
		if( fabs( fun[ i ].x * dex[ x ].x * dex[ x ].x + fun[ i ].y * dex[ x ].x - dex[ x ].y ) < eps ) {
			dfs( x + 1 , num , lon );
			return;
		}
	for( int i = 1 ; i <= lon ; i ++ ) {	//与之前剩下的一只猪组成抛物线
		if( fabs( dex[ x ].x - lone[ i ].x ) < eps ) continue; 
		Paird s = calc( dex[ x ] , lone[ i ] );
		if( s.first < 0 ) {
			fun[ num + 1 ] = { s.first , s.second };
			
			node tmp[ MAXN + 5 ];
			for( int k = i ; k <= lon ; k ++ )
				tmp[ k ] = lone[ k ];
			for( int k = i ; k < lon ; k ++ )
				lone[ k ] = lone[ k + 1 ];
			dfs( x + 1 , num + 1 , lon - 1 );
			for( int k = i ; k <= lon ; k ++ )
				lone[ k ] = tmp[ k ];
		}
	}
	lone[ lon + 1 ] = dex[ x ];		//作为剩下的一只猪
	dfs( x + 1 , num , lon + 1 );
}

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m); Ans = n;
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%lf %lf",&dex[ i ].x,&dex[ i ].y);
		dfs( 1 , 0 , 0 );
		printf("%d\n",Ans);
	}
	return 0;
}